package com.wtgroup.demo.leetcode.q010_正则表达式匹配;

import java.util.ArrayList;
import java.util.List;

/**
 * @author dafei
 * @version 0.1
 * @date 2021/3/26 12:27
 */
public class S_My {

    public static void main(String[] args) {
        // String s = "aa", p = "a";
        // String s = "aa", p = "a*";
        // String s = "ab", p = ".*";
        // String s = "aab", p = "c*a*b";
        // String s = "mississippi", p = "mis*is*p*.";
        // String s = "ab", p = ".*c";
        // String s = "aaa", p = "aaaa";
        String s = "aaa", p = "a*a"; // fail, a* 就已经把文本消耗完了.

        System.out.println(new S_My().isMatch(s, p));
    }

    /**
     * 文本主导
     * TODO fail
     */
    public boolean isMatch(String s, String p) {
        List<P> ps = new ArrayList<>();
        for (int i = 0; i < p.length(); i++) {
            if (i < p.length() - 1 && p.charAt(i+1) == '*') {
                    ps.add(new P(p.charAt(i), 3));
                    i++;
            } else {
                ps.add(new P(p.charAt(i), p.charAt(i) == '.' ? 2 : 1));
            }
        }

        int pi = 0;
        int i = 0;
        P curp = null;
        for (i = 0; i < s.length() && pi < ps.size(); i++) {
            char c = s.charAt(i);
            curp = ps.get(pi);
            if (curp.patternType == 1) {
                if (c != curp.pattern) {
                    return false;
                } else {
                    pi++;
                }
            } else if (curp.patternType == 2) {
                pi++;
            } else if (curp.patternType == 3) {
                if (c == curp.pattern || curp.pattern == '.') {
                    // pi 不移
                } else {
                    // 允许此位置不匹配. pi +1 , 但 i -1, 下一轮, 当前字符和下一个模式匹配
                    pi++;
                    i--;
                }
            }
        }

        if (curp.patternType == 3) { // 哎, 统一大小
            pi++;
        }

        // 两者有一个没有正常结束, 说明都失败了
        return (i < s.length() || pi<ps.size()) ? false : true;
    }

    static class P {
        public char pattern;
        // 1-单字符; 2-'.'; 3-'a*'
        public int patternType;

        public P(char pattern, int patternType) {
            this.pattern = pattern;
            this.patternType = patternType;
        }
    }


    /*char[] ss = s.toCharArray();
        char[] pp = p.toCharArray();

        int pi = 0;
        int i = 0;
        for (i = 0; i < ss.length && pi < pp.length; i++) {
            char cur = ss[i];
            if (cur == pp[pi]) {
                pi++;
            } else if (pp[pi] == '.') {
                pi++;
            } else if (pp[pi] == '*') {
                if (cur != pp[pi-1] && pp[pi-1] != '.') {
                    // 模式向前一位
                    if (pi+1 >= pp.length-1 || cur != pp[pi + 1]) {
                        return false;
                    }
                }
            } else {
                return false;
            }
        }

        return i < ss.length ? false : true; // 文本没有扫描结束, 说明模式不够, false.*/
}
